|
Randomized Logarithmic-space (RL), sometimes called RLP (Randomized Logarithmic-space Polynomial-time),〔A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3):559–578. 1989.〕 is the complexity class of computational complexity theory problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with one-sided error. It is named in analogy with RP, which is similar but has no logarithmic space restriction. The probabilistic Turing machines in the definition of RL never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called ''one-sided error''. The constant 1/3 is arbitrary; any ''x'' with 0 < ''x'' < 1 would suffice. This error can be made 2−''p''(''x'') times smaller for any polynomial ''p''(''x'') without using more than polynomial time or logarithmic space by running the algorithm repeatedly. Sometimes the name RL is reserved for the class of problems solvable by logarithmic-space probabilistic machines in ''unbounded'' time. However, this class can be shown to be equal to NL using a probabilistic counter, and so is usually referred to as NL instead; this also shows that RL is contained in NL. RL is contained in BPL, which is similar but allows two-sided error (incorrect accepts). RL contains L, the problems solvable by deterministic Turing machines in log space, since its definition is just more general. Noam Nisan showed in 1992 the weak derandomization result that RL is contained in SC,〔.〕 the class of problems solvable in polynomial time and polylogarithmic space on a deterministic Turing machine; in other words, given ''polylogarithmic'' space, a deterministic machine can simulate ''logarithmic'' space probabilistic algorithms. It is believed that RL is equal to L, that is, that polynomial-time logspace computation can be completely derandomized; major evidence for this was presented by Reingold et al. in 2005.〔O. Reingold and L. Trevisan and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem, , 2004.〕 A proof of this is the holy grail of the efforts in the field of unconditional derandomization of complexity classes. A major step forward was Omer Reingold's proof that SL is equal to L. == References == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「RL (complexity)」の詳細全文を読む スポンサード リンク
|